package pers.tz.题目.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author irony
 * @date 2024-03-14
 */
public class 面试题_08_07_无重复字符串的排列组合 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(permutation("abc")));
    }

    public static String[] permutation(String S) {
        List<String> ans = new ArrayList<>();
        char[] charArray = S.toCharArray();
        List<Character> rest = new ArrayList<>();
        for (char c : charArray) {
            rest.add(c);
        }

        process(rest, "", ans);

        return ans.toArray(new String[0]);
    }

    public static void process(List<Character> rest, String path, List<String> ans) {
        if (rest.isEmpty()) {
            ans.add(path);
            return;
        }

        int size = rest.size();
        for (int i = 0; i < size; i++) {
            char cur = rest.remove(i);
            process(rest, path + cur, ans);
            // 恢复现场
            rest.add(i, cur);
        }
    }
}
